//https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/submissions/555665748/
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
}
class Solution {
    //定义一个成员变量 存储上一个节点的地址
    private Node prev;//初始值为null

    public Node treeToDoublyList(Node root) {
        if (root == null) {
            return root;
        }
        toJoin(root);
        Node head = root;
        Node tail = root;
        //找头结点
        //转换成双向链表后，链表的头结点就在pRootOfTree的左边
        //头结点的left（前驱）为null
        while (head.left != null) {
            head = head.left;
        }
        //找尾结点
        //转换成双向链表后，链表的尾结点就在pRootOfTree的右边
        //尾结点的right（后继）为null
        while (tail.right != null) {
            tail = tail.right;
        }
        //首尾相连
        head.left = tail;
        tail.right = head;
        return head;
    }

    private void toJoin(Node root) {
        if (root == null) return;
        //中序遍历思想递归
        toJoin(root.left);
        //修改前驱，将当前节点的left域更改为前一个节点的地址
        root.left = prev;
        if (prev != null) {
            //当prev不为空时，修改后继
            //将其right域修改为当前节点的地址（prev本就是当前节点的前驱）
            prev.right = root;
        }
        //更新prev
        prev = root;
        toJoin(root.right);
    }
}
